package com.future;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * Description: 491. 递增子序列
 *
 * @author weiruibai.vendor
 * Date: 2022/12/27 09:46
 */
public class Solution_491 {

    private static Solution_491 instance = new Solution_491();

    public static void main(String[] args) {
        int[] nums = {4, 6, 7, 7};
        List<List<Integer>> ans = instance.findSubsequences_v2(nums);
        for (List list : ans) {
            System.out.println(list);
        }
    }


    public List<List<Integer>> findSubsequences_v2(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        if (nums.length == 1) {
            return ans;
        }
        Set<List<Integer>> res = new HashSet<>();
        process(nums, 0, res, new ArrayList<Integer>());
        return new ArrayList<>(res);
    }

    private void process(int[] nums, int i, Set<List<Integer>> ans, List<Integer> tmp) {
        if (i == nums.length) {
            if (tmp.size() > 1) {
                ans.add(new ArrayList<>(tmp));
            }
            return;
        }
        // 不选择
        process(nums, i + 1, ans, tmp);
        // 选择
        if (tmp.isEmpty() || tmp.get(tmp.size() - 1) <= nums[i]) {
            tmp.add(nums[i]);
            process(nums, i + 1, ans, tmp);
            tmp.remove(tmp.size() - 1);
        }
    }


}
